# LeetCode 23、合并K个升序链表（归并思路）
# 一、题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并K个升序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 如果划分的 lists 总的链表个数为 0
if(lists.length == 0){
// 返回空
return null;
}
// 如果划分的 lists 总的链表个数为 1
if(lists.length == 1){
// 不需要再划分，返回这个链表
return lists[0];
}
// 如果划分的 lists 总的链表个数为 2
if(lists.length == 2){
// 将这两个链表合并
return mergeTwoLists(lists[0],lists[1]);
}
// 计算中点
int mid = lists.length / 2;
// 设置两个存放链表的数组
// sub1 用来存放前部分的那些链表
ListNode[] sub1 = new ListNode[mid];
for(int i = 0 ; i < mid ; i++){
sub1[i] = lists[i];
}
// sub2 用来存放后部分的那些链表
ListNode[] sub2 = new ListNode[lists.length - mid ];
for(int i = mid ; i < lists.length ; i++){
sub2[i - mid] = lists[i];
}
// 获取 sub1 合并之后的结果
ListNode l1 = mergeKLists(sub1);
// 获取 sub2 合并之后的结果
ListNode l2 = mergeKLists(sub2);
// 将这两个链表合并返回
return mergeTwoLists(l1,l2);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode dummy = new ListNode(-1);
// 设置一个指针，指向虚拟节点
ListNode pre = dummy;
// 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while (l1 != null && l2 != null) {
// 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if (l1.val <= l2.val) {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l1
pre.next = l1;
// 让 l1 向后移动
l1 = l1.next;
}else {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l2
pre.next =l2;
// 让 l2 向后移动
l2 = l2.next;
}
// 让 pre 向后移动
pre = pre.next;
}
// 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
// 直接把剩下的节点加入到 pre 的 next 指针位置
// 如果 l1 中还有节点
if (l1 != null) {
// 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l1;
}
// 如果 l2 中还有节点
if (l2 != null) {
// 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l2;
}
// 最后返回虚拟节点的 next 指针
return dummy.next;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并K个升序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 如果划分的 lists 总的链表个数为 0
if(lists.size() == 0){
// 返回空
return NULL;
}
// 如果划分的 lists 总的链表个数为 1
if(lists.size() == 1){
// 不需要再划分，返回这个链表
return lists[0];
}
// 如果划分的 lists 总的链表个数为 2
if(lists.size() == 2){
// 将这两个链表合并
return mergeTwoLists(lists[0],lists[1]);
}
return merge(lists , 0 , lists.size() - 1);
}
private:
ListNode* merge(vector<ListNode*>& lists,int left,int right){
if( left > right ){
return NULL;
}
if( left == right ){
return lists[left];
}
int mid = ( left + right )/2;
return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right));
}
private:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode *dummy = new ListNode(-1);
// 设置一个指针，指向虚拟节点
ListNode *pre = dummy;
// 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while (l1 != NULL && l2 != NULL) {
// 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if (l1->val <= l2->val) {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l1
pre->next = l1;
// 让 l1 向后移动
l1 = l1->next;
}else {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l2
pre->next =l2;
// 让 l2 向后移动
l2 = l2->next;
}
// 让 pre 向后移动
pre = pre->next;
}
// 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
// 直接把剩下的节点加入到 pre 的 next 指针位置
// 如果 l1 中还有节点
if (l1 != NULL) {
// 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre->next = l1;
}
// 如果 l2 中还有节点
if (l2 != NULL) {
// 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre->next = l2;
}
// 最后返回虚拟节点的 next 指针
return dummy->next;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 合并K个升序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:return
return self.merge(lists,0,len(lists) - 1)
def merge(self,lists,left , right ):
if left == right :
return lists[left]
# 计算中点
mid = left + (right - left) // 2
# 获取 l1 合并之后的结果
l1 = self.merge(lists, left, mid)
# 获取 l2 合并之后的结果
l2 = self.merge(lists, mid+1, right)
# 将这两个链表合并返回
return self.mergeTwoLists(l1,l2)
def mergeTwoLists(self, l1, l2):
# 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
dummy = ListNode(-1)
# 设置一个指针，指向虚拟节点
pre = dummy
# 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while l1 and l2:
# 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if l1.val <= l2.val :
# 让 pre 指向节点的 next 指针指向这个更小值的节点
# 即指向 l1
pre.next = l1
# 让 l1 向后移动
l1 = l1.next
else:
# 让 pre 指向节点的 next 指针指向这个更小值的节点
# 即指向 l2
pre.next =l2
# 让 l2 向后移动
l2 = l2.next
# 让 pre 向后移动
pre = pre.next
# 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
# 直接把剩下的节点加入到 pre 的 next 指针位置
# 如果 l1 中还有节点
if l1 != None :
# 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l1
# 如果 l2 中还有节点
if l2 != None :
# 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l2;
# 最后返回虚拟节点的 next 指针
return dummy.next
# 四、复杂度分析
时间复杂度：O(kn×logk)。
空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。